package com.base.graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 210. 课程表 II
 * 现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。
 * <p>
 * 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
 * 返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/course-schedule-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author leon
 * @date 2021年12月14日 18:26
 */
public class FindOrder {
    private List<List<Integer>> edges;
    private int[] indegs;

    /**
     * 广度优先
     */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<>();
        indegs = new int[numCourses];

        for (int i = 0; i < numCourses; i++) {
            edges.add(new LinkedList<>());
        }

        for (int[] e: prerequisites) {
            edges.get(e[1]).add(e[0]);
            indegs[e[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < numCourses; i++) {
            if(indegs[i] == 0){
                queue.add(i);
            }
        }

        int[] res = new int[numCourses];
        int count = 0;
        while (!queue.isEmpty()){
            Integer poll = queue.poll();
            res[count++] = poll;
            for (int e :
                    edges.get(poll)) {
                indegs[e]--;
                if (indegs[e]==0){
                    queue.add(e);
                }
            }
        }
        return count == numCourses?res:new int[0];
    }
}
